package week3;
import java.util.*;

public class Day6 {


    public static void main(String[] args) {
        int[][] arr = {{1,3},{10,4}};
        knapsack(10,2,arr);
    }

    //3.0-1背包
    public static int knapsack (int V, int n, int[][] vw) {
        // write code here
        int[][] dp = new int[n][V+1];
        for(int i=0;i<V+1;i++)
            if(vw[0][0]<=i) dp[0][i]=vw[0][1];
        for(int i=1;i<n;i++)
            for(int j=1;j<V+1;j++) {
                if(vw[i][0]<=j) dp[i][j]=Math.max(dp[i-1][j],vw[i][1]+dp[i-1][j-vw[i][0]]);
                else dp[i][j]=dp[i-1][j];
            }
        return dp[n-1][V];
    }

}
